A New Hybrid Algorithm to Solve Euclidean Plane TSP

doi:10.3969/j.issn.1006-2475.2010.05.010

Computer and Modernization ›› 2010, Vol. 1 ›› Issue (5): 33-35,3.doi: 10.3969/j.issn.1006-2475.2010.05.010

• 人工智能 • Previous Articles Next Articles

A New Hybrid Algorithm to Solve Euclidean Plane TSP

WANG Xing-qi, XUE Xiao-chun

School of Aeronautic Science and Engineering, Beihang University, Beijing 100191, China

Received:2009-11-30 Revised:1900-01-01 Online:2010-05-10 Published:2010-05-10

Abstract

Abstract: Traveling salesman problem(TSP) is a classic combinatorial optimization problem. This paper uses an insertion method which is based on convex polygon to form loop, then applies the adjustment algorithm to shorten the loop. At last the paper uses the crossover operator which is from the genetic algorithm to optimize the loop. The result of calculation shows that the method has high precision and good practicability.

Key words: TSP, combinatorial optimization, convex polygon, crossover operator

CLC Number:

TP301.6

WANG Xing-qi;XUE Xiao-chun. A New Hybrid Algorithm to Solve Euclidean Plane TSP[J]. Computer and Modernization, 2010, 1(5): 33-35,3.

[1]	LIU Ya-wen, JIANG Yan, PAN Da-zhi. Improved Binary Harmony Search Algorithm for Solving Multidimensional Knapsack Problem [J]. Computer and Modernization, 2022, 0(08): 13-19.
[2]	WANG Hong. Kriging Parameter Estimation Algorithm Based on Combinatorial Optimization [J]. Computer and Modernization, 2021, 0(09): 51-56.
[3]	YANG Wen-liang, FENG Hui-fang. Analysis of Spatio-temporal Interaction Characteristics of Urban Area Based on Taxi GPS Trajectory [J]. Computer and Modernization, 2021, 0(01): 87-93.
[4]	YE Jia-qi1, FU Qiang1,2, HE Yi-jia1, YE Hao1 . Ant Colony Algorithm Based on Clustering Integration for Solving Large-scale TSP Problems [J]. Computer and Modernization, 2020, 0(02): 31-.
[5]	LIU Zhi-yong 1,2, ZHOU Jie 1, ZHANG Lin3,ZHANG Jia-xin1, ZHANG Qian1, SHA Ren1. Research on TSP Problem Based on Crossover and Mutation Combination [J]. Computer and Modernization, 2018, 0(03): 54-.
[6]	PAN Cheng-hao, GUO Min. Batch Picking Path Planning Simulation of Warehouse Mobile Robot [J]. Computer and Modernization, 2017, 0(2): 12-16.
[7]	FENG Jun, WANG Chun, ZHU Kang-kang, WEI Tong-tong. Replication Migration Technology for Access Hotspots Based on Hadoop [J]. Computer and Modernization, 2016, 0(1): 108-113.
[8]	LI Qian1, HE Xing-shi1, YANG Xin-she1,2. A Discrete Flower Pollination Algorithm for Travelling Salesman Problem [J]. Computer and Modernization, 2016, 251(07): 37-43.
[9]	LEI Yumei. A Solution of Largescale TSP Based on Improved Genetic Algorithm [J]. Computer and Modernization, 2015, 0(2): 34-.
[10]	ZHENG Bo-chuan. A Lotka-Volterra Recurrent Neural Network Model for Solving TSP [J]. Computer and Modernization, 2013, 1(8): 204-208.
[11]	CHU Dian;JIANG Chunhua;HAO Zongbo;JIANG Wei. Video Surveillance System Based on SIP, RTP/RTCP and RTSP  [J]. Computer and Modernization, 2013, 1(11): 139-142.
[12]	LI Chun-lei;MO Rong;FAN Di. Structure and Performance of Two-stage Composite Genetic Algorithm [J]. Computer and Modernization, 2012, 1(10): 5-7,13.
[13]	MA Xiao-hui;WANG Hong;. Application of Improved PSO in TSP [J]. Computer and Modernization, 2011, 193(9): 5-7,11.
[14]	HUANG De-hui;LIANG Peng;ZENG Hua. Design and Implementation of Mobile Phone Embedded RTSP Streaming Media Server Based on MX27 [J]. Computer and Modernization, 2011, 7(7): 78-81.
[15]	YE An-xin. Research on Traveling Salesman Problem Based onImproved Particle Swarm Optimization Algorithm [J]. Computer and Modernization, 2011, 1(4): 1-3.

A New Hybrid Algorithm to Solve Euclidean Plane TSP

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments